package org.zlb.algorithm.tree;

/**
 * 二叉查找树
 * 
 * @author zhoulingbo
 *
 * @param <Key>
 * @param <Value>
 */
public class BSTree<Key extends Comparable<Key>, Value> {

	private Node root;
	
	private class Node {
		private Key key;
		private Value val;
		private Node left, right;
		private int N;
		
		public Node(Key key, Value val, int N) {
			this.key = key;
			this.val = val;
			this.N = N;
		}
	}
	
	/**
	 * 树的节点数
	 * @return
	 */
	public int size() {
		return size(root);
	}
	
	private int size(Node node) {
		if (node == null)
			return 0;
		return node.N;
	}
	
	/**
	 * 获取key节点的值
	 * @param key
	 * @return
	 */
	public Value get(Key key) {
		if (key == null)
			return null;
		
		return get(root, key);
	}
	
	private Value get(Node node, Key key) {
		if (node == null)
			return null;
		
		int c= key.compareTo(node.key);
		if (c == 0) {
			return node.val;
		} else if (c < 0) {
			return get(node.left, key);
		} else {
			return get(node.right, key);
		}
	}
	
	/**
	 * 插入key节点值，如果存在则更新
	 * @param key
	 * @param val
	 */
	public void put(Key key, Value val) {
		root = put(root, key, val);
	}
	
	private Node put(Node node, Key key, Value val) {
		if (node == null) {
			node = new Node(key, val, 1);
			return node;
		}
		
		int c= key.compareTo(node.key);
		if (c == 0) {
			node.val = val;
		} else if (c < 0) {
			put(node.left, key, val);
		} else {
			put(node.right, key, val);
		}
		
		node.N = size(node.left) + size(node.right) + 1;
		return node;
	}
	
	/**
	 * 返回最大键
	 * @return
	 */
	public Key max() {
		return max(root).key;
	}
	
	private Node max(Node node) {
		if (node.right == null)
			return node;
		
		return max(node.right);
	}
	
	/**
	 * 返回最小键
	 * @return
	 */
	public Key min() {
		return min(root).key;
	}
	
	private Node min(Node node) {
		if (node.left == null)
			return node;
		
		return min(node.left);
	}
	
	/**
	 * 查找排名k的键
	 * @param k
	 * @return
	 */
	public Key select(int k) {
		return select(root, k).key;
	}
	
	private Node select(Node node, int k) {
		if (node == null)
			return null;
		
		int t = size(node.left);
		if (t > k) {
			return select(node.left, k);
		} else if (t < k) {
			return select(node.right, k-t-1);
		} else {
			return node;
		}
	}
	
	/**
	 * 键key的排名
	 * @param key
	 * @return
	 */
	public int rank(Key key) {
		return rank(root, key);
	}
	
	private int rank(Node node, Key key) {
		if (node == null)
			return -1;
		
		int c = key.compareTo(node.key);
		if (c < 0) {
			return rank(node.left, key);
		} else if (c > 0) {
			return 1 + size(node.left) + rank(node.right, key);
		} else {
			return size(node.left);
		}
	}
	
	/**
	 * 删除最小节点
	 */
	public void deleteMin() {
		root = deleteMin(root);
	}
	
	private Node deleteMin(Node node) {
		if (node.left == null) {
			return node.right;
		}
		
		node.left = deleteMin(node.left);
		node.N = size(node.left) + size(node.right) + 1;
		return node;
	}
	
	public void delete(Key key) {
		root = delete(root, key);
	}
	
	private Node delete(Node node, Key key) {
		int c = key.compareTo(node.key);
		if (c < 0) {
			node.left = delete(node.left, key);
		} else if (c > 0) {
			node.right = delete(node.right, key);
		} else {
			if (node.left == null)
				return node.right;
			if (node.right == null)
				return node.left;
			Node t = node;
			node = min(node.right);
			node.right = deleteMin(t.right);
			node.left = t.left;
		}
		
		node.N = size(node.left) + size(node.right) + 1;
		return node;
	}
	
}
